public class Solution115 {
    public int numDistinct(String s, String t) {
        int[][] f=new int[t.length()+1][s.length()+1];
        for (int i=0;i<=s.length();i++){
            f[0][i]=1;
        }
        for (int i=1;i<=t.length();i++){
            int sum=0;
            for (int j=1;j<=s.length();j++){
                if (s.charAt(j-1)==t.charAt(i-1)){
                    sum+=f[i-1][j-1];
                }
                f[i][j]=sum;
            }
        }
        return f[t.length()][s.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution115().numDistinct("babgbag","bag"));
    }
}
